#ifndef _QUICKSORT_H
#define _QUICKSORT_H

#include <iostream>
#include <vector>
#include <cstdlib>
#include <random>

template <typename Comparable>
void InsertSort(std::vector<Comparable>& A,int m,int n)
{
	for (int j=m+1; j<=n; j++)
	{
		Comparable key = A[j];
		int i = j-1;
		while (i>=m && A[i]>key)
		{
			A[i+1] = A[i];
			i--;
		}
		A[i+1] = key;
	}
}

template <typename Comparable>
void InsertSort(std::vector<Comparable>& A)
{
	InsertSort(A,0,A.size()-1);
}

template <typename Comparable>
int findkey(std::vector<Comparable>& A)
{
	int n = A.size()-1;
	int m = n/2;
	if(n < 3) return 0;
	if(A[0] > A[n]){
		if(A[0] < A[m]) return 0;
		else if(A[m] > A[n]) return m;
		else return n;
	}else if(A[n] < A[m]) return n;
	else if(A[m] > A[0]) return m;
	else return 0;
}

template <typename Comparable>
void swap(Comparable& a,Comparable& b)
{
	Comparable t = a;
	a = b;
	b = t;
}

template <typename Comparable>
const Comparable & median3(std::vector<Comparable>& a, int l, int r)
{
	int c = (l + r)/2;
	if(a[c] < a[l]) swap(a[l],a[c]);
	if(a[r] < a[l]) swap(a[l],a[r]);
	if(a[r] < a[c]) swap(a[c],a[r]);

	swap(a[c],a[r-1]);
	return a[r-1];

}

template <typename Comparable>
int partion(std::vector<Comparable>& A, int m, int n)
{
	Comparable pivot = median3(A,m,n);
	int i=m,j= n-1;
	while (1)
	{
		while (A[++i] < pivot){}
		while (pivot < A[--j]){}
		if (i < j)
			swap(A[i],A[j]);
		else 
			break;
	}
		swap(A[i],A[n-1]);
		return i;
}

template <typename Comparable>
void quickSort(std::vector<Comparable>& A, int m, int n)
{
	if (m + 10 < n)
	{
		int q = partion(A, m, n);
		quickSort(A, m, q-1 );
		quickSort(A, q + 1, n);
	}
	else 
		InsertSort(A,m,n);
}

template <typename Comparable>
void sort(std::vector<Comparable>& A)
{
    quickSort(A,0,A.size()-1);
}

///以下为随机选取pivot的快排

template <typename Comparable>
const Comparable & randpivot(std::vector<Comparable>& a, int l, int r)
{
    srand((unsigned)time(NULL));
	int c = rand()%(r-l);
	swap(a[c],a[r]);
	return a[r];

}

template <typename Comparable>
int randpartion(std::vector<Comparable>& A, int m, int n)
{
	Comparable pivot = randpivot(A,m,n);
	int i=m-1,j= n;
	while (1)
	{
		while (A[++i] < pivot){}
		while (pivot < A[--j]){}
		if (i < j)
			swap(A[i],A[j]);
		else 
			break;
	}
		swap(A[i],A[n]);
		return i;
}

template <typename Comparable>
void randquickSort(std::vector<Comparable>& A, int m, int n)
{
	if (m + 10 < n)
	{
		int q = randpartion(A, m, n);
		randquickSort(A, m, q-1 );
		randquickSort(A, q + 1, n);
	}
	else 
		InsertSort(A,m,n);
}

template <typename Comparable>
void randsort(std::vector<Comparable>& A)
{
    randquickSort(A,0,A.size()-1);
}

#else
///Do Nothing
#endif